// 使用方向数组控制遍历方向，记录访问过的格子，遇到越界或已访问则右转，直到遍历完所有元素。
// step 1# 定义方向数组：右→下→左→上（顺时针方向）
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};  // 每个方向的行列偏移
int *res;     // 返回结果数组（后面动态分配）
int **used;   // 标记是否访问过该格子（辅助二维数组）

// step 2# 主函数：按照顺时针螺旋顺序遍历矩阵并返回结果
int* spiralOrder(int** matrix, int matrixSize, int* matrixColSize, int* returnSize) {
    int row = matrixSize;           // 行数
    int col = matrixColSize[0];     // 列数（题目保证每行相等）

    // step 3# 初始化结果数组 res 和标记数组 used
    res = (int *)malloc(sizeof(int) * row * col);             // 分配结果数组
    used = (int **)malloc(sizeof(int *) * row);               // 分配行指针数组
    for (int i = 0; i < row; i++) {
        used[i] = (int *)calloc(col, sizeof(int));            // 初始化每一行为全 0
    }

    int count = 0;          // 当前已写入结果数组的元素数量
    int curX = 0, curY = 0; // 当前访问的坐标位置
    int dirIndex = 0;       // 当前方向（0:右，1:下，2:左，3:上）

    // step 4# 开始遍历矩阵，直到填满结果数组
    while (count < row * col) {
        used[curX][curY] = 1;                 // 标记当前位置已访问
        res[count++] = matrix[curX][curY];    // 写入结果数组

        // step 5# 计算下一个位置
        int nextX = curX + dir[dirIndex][0];
        int nextY = curY + dir[dirIndex][1];

        // step 6# 如果越界或已访问，则右转一个方向
        if (nextX < 0 || nextX >= row || nextY < 0 || nextY >= col || used[nextX][nextY]) {
            dirIndex = (dirIndex + 1) % 4;  // 顺时针换方向
            nextX = curX + dir[dirIndex][0];
            nextY = curY + dir[dirIndex][1];
        }

        // step 7# 移动到下一个合法位置
        curX = nextX;
        curY = nextY;
    }

    // step 8# 设置返回数组长度
    *returnSize = row * col;

    return res;  // 返回螺旋遍历结果数组
}
